package com.sourcestruct.linearlist;

import lombok.ToString;

/**
 * @author: ZhouBert
 * @date: 2019/6/8
 * @description: 顺序队列 入队，出队，支持扩容
 */
@ToString
public class ArrayQueue<T> {

	private T[] data;
	/**
	 * 实际大小
	 */
	private int size;
	/**
	 * 队列头（初始为0）
	 */
	private int head;
	/**
	 * 队列尾(初始为-1)
	 */
	private int tail;

	public ArrayQueue(int capacity) {
		data = (T[]) new Object[capacity];
		size = 0;
		head = 0;
		head = 0;
		tail = -1;
	}

	/**
	 * 入队
	 *
	 * @param obj
	 */
	public void queue(T obj) {
///		if (size==data.length){
///			throw new IllegalArgumentException(String.format("队伍长度超出限制！此时队伍长度为 %d",size));
///		}
		///当尾指针指向最后节点时，进行数组拷贝，申请一个长度为 2*size 的数组
		if (tail == size - 1) {
			resize();
		}
		data[size++]=obj;
		tail++;
	}

	/**
	 * 出队
	 * @return
	 */
	public T dequeue(){
		if (size==0){
			throw new IllegalArgumentException("队列为空！");
		}
		head++;
		return data[head-1];
	}

	/**
	 * 重新申请空间，拷贝数组
	 */
	private void resize() {
		///1.重新申请数组长度，为现长度的两倍
		T[] newData = (T[]) new Object[2 * size];
		///2.拷贝原数组
		for (int i = head, ni = 0; i <= tail; i++) {
			newData[ni] = data[i];
		}
		data = newData;
		head=0;
		tail=size-1;
	}

	public static void main(String[] args) {
		ArrayQueue<Integer> queue = new ArrayQueue(10);
		queue.queue(1);
		queue.queue(2);
		queue.queue(20);
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
	}
}
